package com.share.algorithm.rescursive;

/**
 * @desc: 加法递归  斐波拉契数列
 * @author:caifan
 * @date:2020/8/9
 */
public class AddRescursive {

    public static void main(String[] args) {
//        for (int i=1;i<=10;i++) {
        long start1 = System.currentTimeMillis();
        System.out.println(fab(35) + "：耗时:" + (System.currentTimeMillis() - start1));
//        }
        long start2 = System.currentTimeMillis();
        System.out.println(fabLoop(35) + "耗时：" + (System.currentTimeMillis() - start2));
        long start3 = System.currentTimeMillis();
        System.out.println(tailFab(35, 1, 1) + "耗时：" + (System.currentTimeMillis() - start3));
    }

    /**
     * 普通递归
     * @param n
     * @return
     */
    public static Integer fab(Integer n) {
        if (n <= 1) {
            return 1;
        }
        if (n <= 2) {
            return n;
        }
        return fab(n - 1) + fab(n - 2);
    }

    /**
     * 尾递归  0 1  1 2 2 3 3 5
     * @return
     */
    public static Integer tailFab(Integer n, Integer res1, Integer res2) {
        if (n == 0) {
            return res1;
        } else {
            return tailFab(n - 1, res2, res1 + res2);
        }
    }

    public static Integer fabLoop(Integer n) {
        Integer[] arr = new Integer[n];
        for (int i=0;i<n;i++) {
            if (i < 2) {
                arr[i] = 1;
            } else {
                arr[i] = arr[i - 1] + arr[i - 2];
            }
        }
        return arr[n - 1] + arr[n - 2];
    }
}
